package com.heima.algorithm.sort;

/**
 * <strong>堆排序</strong>
 * <p>思想：将待排序数组建堆heapify，大顶堆，然后每次删除堆顶元素，其过程就是将堆顶元素交换到数组末尾，然后size--，当堆中只有一个元素或者全部删除，则排序完成</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/28 18:44
 */
public class HeapSort {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(NlogN)，平均情况：O(NlogN)，空间复杂度：O(1)，稳定：否，思想：比较
    //（3）堆排序的辅助性较强，理解前先理解堆的数据结构

    /**
     * 大顶堆
     */
    static class MaxHeap {
        int[] arr; // 堆数组
        int size; // 堆中元素个数

        /**
         * 构造堆
         * @param arr 数组
         */
        MaxHeap(int[] arr) {
            this.arr = arr;
            this.size = arr.length;
            heapify();
        }

        /**
         * 堆化
         */
        private void heapify() {
            // 弗洛伊德建堆
            // 找到最后一个有叶子节点的节点，(size - 1 - 1) / 2 => size / 2 - 1
            for (int i = (size >> 1) - 1; i >= 0; i--) {
                down(i);
            }
        }

        /**
         * 下潜
         * @param parent 当前下潜节点
         */
        private void down(int parent) {
            int left = 0;
            int right = 0;
            while (true) {
                left = parent * 2 + 1;
                right = left + 1;
                int max = max(parent, left, right);
                if (max == parent) {
                    break;
                }
                swap(parent, max);
                parent = max;
            }
        }

        /**
         * 找到三个节点中的最大值
         * @param parent 父节点
         * @param left 左节点
         * @param right 右节点
         * @return 节点下标
         */
        private int max(int parent, int left, int right) {
            if (left >= size) {
                return parent;
            } else if (right == size) {
                return arr[parent] >= arr[left] ? parent : left;
            } else {
                return arr[parent] >= arr[left] ? (arr[parent] >= arr[right] ? parent : right) : (arr[left] >= arr[right] ? left : right);
            }
        }

        /**
         * 交换两个元素的值
         * @param index1 元素1下标
         * @param index2 元素2下标
         */
        private void swap(int index1, int index2){
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

        /**
         * 删除堆顶元素
         */
        void poll(){
            swap(0, --size);
            down(0);
        }
    }

    public static void heapSort(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        for (int i = 0; i < arr.length - 1; i++) {
            maxHeap.poll();
        }
    }
}
